class Solution02 {
	/** 非递归中序遍历 */
	public TreeNode increasingBST(TreeNode root){
		Deque<TreeNode> stack = new ArrayDeque<>();
		TreeNode curNode = root;
		TreeNode preNode = null;
		TreeNode firstNode = null;

		while(!stack.isEmpty() || curNode != null){
			while(curNode != null){
				stack.offerLast(curNode);
				curNode = curNode.left;
			}
			curNode = stack.pollLast();
			if(preNode != null){
				preNode.right = curNode;
			} else {
				firstNode = curNode;
			}
			preNode = curNode;
			curNode.left = null;
			curNode = curNode.right;
		}
		return firstNode;
	}
}
